package algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by liuwei on 2018/3/12.
 */
public class NQueenJava {

    static int res2 ;
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        int[] queenList = new int[n];//第i个位置存放的数表示row行时，Q的列
        putQ(queenList,0,n,res);//第0行开始就放Q
        return res;
    }

    private static void  putQ(int[] queenList ,int row,int n,List<List<String>> res){
        if(row == n){
            List<String> list = new ArrayList<>();
            for(int i = 0; i < n; i++){
                String str = "";
                for (int j = 0; j < n; j++) {
                    if (j !=queenList[i]) str += ".";
                    else str += "Q";
                }
                list.add(str);
            }
            res.add(list);
        }
       for(int i=0;i<n;i++) {//每列开始
           if (isValid(queenList, i, row)) {
               queenList[row] = i;
               putQ(queenList,row+1,n,res);
           }
       }


    }


    private static boolean isValid(int[] queenList, int column, int row) {
        for (int i = 0; i < row; i++) {
            int pos = queenList[i];//Q处于第几行

            //每列
            if (column == pos) {
                return false;
            }
            //右对角线
            if (column - row == pos - i) {
                return false;
            }
            //左对角线
            if (column + row == pos + i) {
                return false;
            }

        }
        return true;
    }

    public int totalNQueens(int n) {
//        int res =0;
        res2 = 0;
        int[] queenList = new int[n];//第i个位置存放的数表示row行时，Q的列
        putQ2(queenList,0,n);//第0行开始就放Q
        return res2;
    }

    private static void  putQ2(int[] queenList ,int row,int n){
        if(row == n){
            res2 += 1;
        }
        for(int i=0;i<n;i++) {//每列开始
            if (isValid(queenList, i, row)) {
                queenList[row] = i;
                putQ2(queenList,row+1,n);
            }
        }


    }


    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new ArrayList<>();
        int left = 0;
        int right = 0;
        int top = 0;
        int bottom = 0;
        int m = matrix.length;//row size
        int n = matrix[0].length;//column size
        while(true){
            //top
            for(int i = 0 ; i< n-left-right ;i++){
                list.add(matrix[top][i+left]);
            }
            top++;
            if(top+bottom == m) break;
            //right
            for(int j =0 ;j< m - top-bottom;j++){
                list.add(matrix[top+j-1][n-right]);
            }
            right++;
            if(left+right == n) break;
            //bottom
            for(int  x= n-right ; x > left ;x--){
                list.add(matrix[m-bottom-1][x+left]);
            }
            bottom++;
            if(top+bottom == m) break;
            //left
            for(int y =m-bottom ;y> top;y--){
                list.add(matrix[y][left]);
            }
            left++;
            if(left+right == n) break;

        }

        return list;
    }

    public boolean canJump(int[] nums) {
        int n = nums.length;
        int maxJump =0;
        for(int i = 0;i<n ;i++){
            if(i > maxJump || maxJump >= (n-1)) break;
            maxJump = Math.max(maxJump,i+nums[i]);
        }
        return maxJump >= (n-1);
    }

    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        if(n ==0 )return matrix;
        int top = 0;
        int bottom = 0;
        int left = 0 ;
        int right = 0 ;
        int k = 1;
        boolean flag = true;
        while(flag){

            //top
            for(int i=left;i<n-top;i++){
                matrix[top][i] = k;
                k++;

            }
            top++;
            if(top + bottom ==n ) break;
            //right
            for(int i = top;i<n-bottom;i++){
                matrix[i][n-right-1] = k;
                k++;

            }
            right++;
            if(left + right ==n ) break;
            //bottom
            for(int i = n-right-1;i>=left;i--){
                matrix[n-bottom-1][i] = k;
                k++;

            }
            bottom++;
            if(top + bottom ==n ) break;
            //left
            for(int i = n-bottom-1;i>top;i--){
                matrix[i][left] = k;
                k++;

            }
            left++;
            if(left + right ==n ) break;
        }
        return matrix;
    }

    public int[] plusOne(int[] digits) {
        int n =digits.length;
        int ans =0;//进位
        for(int i=0;i<n;i++){
            if(i==0){
               if (digits[n-1]+1 != 10){
                   digits[n-1] += 1;
                   break;
               }else{
                   digits[n-1] =0;
                   ans = 1;
               }
            }else if(digits[n-i-1]+ans == 10){
                digits[n-i-1] =0;
                ans = 1;
            }else{
                digits[n-i-1] +=1;
                break;
            }
        }
        if(digits[0] ==0){
            int[] arr = new int[n+1];
            Arrays.fill(arr,0);
            arr[0] = 1;
            return arr;
        }
        return digits;

    }
    public  static void  main(String [] args) {
        int[] arr ={9};
//        Arrays.fill(arr,0);
//        int[] arr2 = Arrays.copyOf(arr,5);
       int res = new NQueenJava().totalNQueens(17);
        System.out.println(res);
    }

}
